/*
 * @lc app=leetcode.cn id=518 lang=java
 *
 * [518] 零钱兑换 II
 */

// @lc code=start
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){//完全背包，从左往右，可以保证每个物品可以被重复挑选
                dp[j]+=dp[j-coins[i]];//装满背包有几种方法
            }
        }
        return dp[amount];
    }
}
// @lc code=end

